package bfs;

import java.util.HashSet;
import java.util.Set;


//解题关键： 将本题抽象成权值为1的最小路径问题
public class 最小基因变化 {
	public static int l,r;
    public static int MAXN=11;
    public static String[] queue=new String[MAXN];

    //仔细读题： 一个字符的改变就是一次基于变化，而有效的基于变化一定在基于库中，
    //         =>一个字符改变时，如果其是有效的，那么其一定在基因库中
    //         =>基因变化是一个字符一个字符变化的
    public int minMutation(String startGene, String endGene, String[] bank) {
        Set<String> visit=new HashSet<>(); //记录访问过的字符串
        Set<String> hash=new HashSet<>();  //记录基因库中的字符串
        for(String s:bank) hash.add(s);

        //如果前后基因一致，直接返回
        if(startGene.equals(endGene)) return 0;
        //如果end不在基因库，直接返回
        if(!hash.contains(endGene))   return -1;

        //替换序列
        char[] change=new char[]{'A','C','G','T'};

        l=r=0;
        //最小变化次数
        int step=0;

        //队列模拟bfs
        queue[r++]=startGene;
        visit.add(startGene);

        while(l<r){
            step++;
            int size=r-l;
            for(int i=0;i<size;i++){
                String s=queue[l++];
                //枚举字符串的每个位置
                for(int j=0;j<s.length();j++){
                    char[] tmp=s.toCharArray();

                    //由于每次基于变化只能变一个字符，因此枚举每个变化
                    //枚举每个位置的可能的字符(A,C,G,T)
                    for(int k=0;k<change.length;k++){
                        //将j位置替换为指定字符
                        tmp[j]=change[k];
                        //获取替换后的字符
                        String ret=new String(tmp);
                        //如果替换后即为end，则返回操作数
                        if(ret.equals(endGene)){
                            return step;
                        }
                        //如果字符串未出现过并且基因库中有该字符串
                        if(visit.contains(ret)==false&&hash.contains(ret)==true){
                            queue[r++]=ret;
                            visit.add(ret);
                        }
                    }
                }
            }
        }
        return -1;
    }
}
